package fpTree;

import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

public class TreeMethods
{
	public static void initialiseLinkedHashMap(Map<Integer, Node> headerTable, List<Integer> fList)
	{
		for (int i = fList.size() - 1; i >= 0; i--)
		{
			headerTable.put(fList.get(i), null);
		}
	}
	
	/**
	 * Index of the list becomes values, list values becomes keys. 
	 */
	public static Map<Integer, Integer> listToMap(List<Integer> list)
	{
		Map<Integer, Integer> fListMap = new HashMap<Integer, Integer>();
		for (int i = 0; i < list.size(); i++)
		{
			fListMap.put(list.get(i), i);
		}
		return fListMap;
	}
	
	public static void processTransaction(List<Integer> transaction, int frequency, Node root,
									Map<Integer, Node> headerTable, Map<Integer, Node> headerTableLast,
									final Map<Integer, Integer> fListMap)
	{
		retainItemsInList(transaction, fListMap.keySet());
		
		// sort the transaction according to order in fList(fListMap)
		// System.out.println("unsorted: " + transaction);
		Collections.sort(transaction, new Comparator<Integer>()
		{
			@Override
			public int compare(Integer s1, Integer s2)
			{
				return fListMap.get(s1) - fListMap.get(s2);
			}
		}); // sort items in this transaction
		
		Node current = root;
		for (int item : transaction)
		{
			// look for the right child to increment, if one exists
			if (current.getChildren().containsKey(item))
			{ // if child exists, increment count
				current = current.getChildren().get(item); 
				current.setCount(current.getCount() + frequency);
			} else
			{ // if it does not, create a child
				Node nn = new Node();
				nn.itemName = item;
				nn.setCount(frequency); // initialise count
				current.getChildren().put(item, nn); // add new node to parent
				nn.parent = current; // add parent to new node
				
				// add node-link
				// headerTable.get(string).add(nn);
				
				// have to test with null and not containsKey because
				// headerTable has been initialised
				if (headerTable.get(item) == null)
				{
					// System.out.println("adding first");
					headerTable.put(item, nn);
				}
				if (!headerTableLast.containsKey(item))
				{
					headerTableLast.put(item, nn);
				} else
				{
					headerTableLast.put(item, nn).setNodeLink(nn);
				}
				
				current = nn;
			}
		}
	}

	public static void retainItemsInList(Collection<Integer> itemset, final Collection<Integer> includeList)
	{
		for (Iterator<Integer> i = itemset.iterator(); i.hasNext();)
		{
			int s = i.next();
			if (!includeList.contains(s))
			{
				i.remove();
			}
		}
	}
	
	/**
	 * @param n 
	 * @param items sorted by decreasing frequency
	 * @return <tt>true</tt> if the ancestors of n (excluding n itself) include all items in <tt>items</tt>.
	 * 			<tt>false</tt> otherwise
	 */
	public static boolean existsInAncestors(Node n, List<Integer> items)
	{
		int remainingIndex = items.size() - 1;
		for (n = n.parent; n.itemName != -1 && remainingIndex >= 0; n = n.parent)
		{
//			System.out.println(items.get(remainingIndex) + ", " + n.itemName + " equals: " + items.get(remainingIndex).equals(n.itemName));
			if (items.get(remainingIndex).equals(n.itemName))
				remainingIndex--;
		}
		
		if (remainingIndex == -1)
			return true;
		
		return false;
	}
	

}
